package BinarySearch;

public class BinarySearchDemo1 {
    public static void main(String[] args) {

        //二分查找/折半查找//核心:
        //每次排除一半的查找范围
        //需求:定义一个方法利用二分查找,查询某个元素在数组中的索引
        //数据如下:{7,23,79,81,103,127,131,147}

        int[] arr ={7,23,79,81,103,127,131,147};
        int target = 131;
        System.out.println(binarySearch(arr, target));//6
        target = 23;
        System.out.println(binarySearch(arr, target));//1
        target = 78;
        System.out.println(binarySearch(arr, target));//-1

        //二分查找的变式一
        //插值查找
        //改变mid的计算方式
        //mid = min + (target - arr[min]) / (arr[max] - arr[min]) + (max - min)
        //适用于数据均匀分部，否则会比二分查找更慢

        //二分查找的变式二
        //斐波那契查找
        //mid = min + 黄金分割点左半边长度 - 1

    }

    public static int binarySearch(int[] arr, int target) {
        //1.定义两个变量记录要查找的范围
        int min = 0;
        int max = arr.length - 1;

        //2.利用循环不断的去找要查找的数据
        while (min <= max) {
            //3.找到min和max的中间位置
            int mid = (min + max) / 2;
            if (arr[mid] > target) {
                max = mid - 1;
            }else if (arr[mid] < target) {
                min = mid + 1;
            }else {
                return mid;
            }

        }
        return -1;
    }

}
